package 剑指Offer专项突破;

/**
 * @Author zhang lei
 * @Date 2021-12-01 13:02
 * 二分查找相关
 */
public class Algo72 {
    public static void main(String[] args) {
        System.out.println(mySqrt(3));

        System.out.println(minEatingSpeed   (new int[]{312884470}, 968709470));
    }
    public static int mySqrt(int x) {
        int left = 1;
        int right = x;
        while (left<=right) {
            int mid = (left+right)/2;

            //【重点】注意点，这里比较的写法
            if(mid <= x/mid) {
                if((mid+1) > x/(mid +1)) {
                    return mid;
                }
                left = mid+1;
            }else {
                right = mid-1;
            }
        }
        return x;
    }

    /**
     * 狒狒吃香蕉
     * @param piles
     * @param h
     * @return
     */
    public static int minEatingSpeed(int[] piles, int h) {
        int max = 0;
        for (int i = 0; i < piles.length; i++) {
            max = Math.max(max, piles[i]);
        }

        int left = 1;
        int right = max;
        while (left<=right) {
            int mid = left + (right - left) /2;
            if(getTimes(piles, mid)<=h) {
                if(mid == 1 || getTimes(piles, mid-1)>h) {
                    return mid;
                }
                right = mid-1;
            }else {
                left = mid+1;
            }
        }
        return -1;
    }

    private static int getTimes(int[] piles, int mid) {
        int h = 0;
        for (int i = 0; i < piles.length; i++) {
            h += (piles[i]+mid-1)/mid;
        }
        return h;
    }
}
